class Solution {
    public int findDuplicate(int[] nums) {
        int left = 0;
        int right = 0;
        do{
            left = nums[left];
            //走两步
            right = nums[nums[right]];
        }while(left != right);

        left = 0;
        while(left!=right) {
            left = nums[left];
            right = nums[right];
        }
        return left;
        
    }
}